package xiaohu.day1.HJ16;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int limitMoney = in.nextInt();// 预算
            int n = in.nextInt();// 物品数量
            List<Goods> goodsList = new ArrayList<Goods>();
            for (int i = 0; i < n; i++) {
                int price = in.nextInt();
                int value = in.nextInt() * price;
                int type = in.nextInt();
                Goods goods = new Goods(i + 1, price, value, type);
                goodsList.add(goods);
            }
            ShoppingPlan shoppingPlan = calculateMaxValue(goodsList, limitMoney);
            System.out.println(shoppingPlan.getTotalValue());
        }
    }

    public static ShoppingPlan calculateMaxValue(List<Goods> goodsList,
                                                 int limitMoney) {
        // 最大公约数
        int gcd = getArrayGcd(goodsList);
        int n = goodsList.size();
        int m = limitMoney / gcd;
        ShoppingPlan[][] dp = new ShoppingPlan[n + 1][m + 1];
        // 初始化边界
        dp[0][0] = new ShoppingPlan();
        for (int i = 1; i <= n; i++) {
            dp[i][0] = dp[0][0];
        }
        for (int j = 1; j <= m; j++) {
            dp[0][j] = dp[0][0];
        }
        // 计算动态规划矩阵
        for (int i = 1; i <= n; i++) {
            Goods goods = goodsList.get(i - 1);
            for (int j = 1; j <= m; j++) {
                // 构建新的购物方案
                ShoppingPlan plan = new ShoppingPlan();
                // 基础方案的索引值
                int planIndex = j - goods.getPrice() / gcd;
                // 是否附件
                if (goods.isAttachment()) {
                    // 索引之需大于等于0，购买的钱才是足够的
                    if (planIndex >= 0) {
                        // 获取主件
                        Goods mainGoods = goodsList.get(goods.getType() - 1);
                        // 判断选取的基础方案是否有主件，决定是否添加主件
                        boolean hasMainGoods = dp[i - 1][planIndex].hasMainGoods(goods);
                        if (!hasMainGoods) {
                            // 如果选取的基础方案没有购买主件，则需要腾出购买主件的钱，需要将基础方案再往前推
                            planIndex -= mainGoods.getPrice() / gcd;
                        }
                        // 腾出钱之后，看看够不够买，如果不够，那就不使用基础方案了，使用新方案从头开始
                        if (planIndex >= 0) {
                            // 前如果够那就复制一份基础方案
                            plan = dp[i - 1][planIndex].createSnapshot();
                        }
                        // 然后再加上买主件
                        if (!hasMainGoods) {
                            plan.addGoods(mainGoods);
                        }
                    }
                } else {
                    // 主件处理
                    if (planIndex >= 0) {
                        // 只需要判断钱够不够就行了，方案的索引大于0，就是够钱出方案，复制一份基础方案继续购买
                        plan = dp[i - 1][planIndex].createSnapshot();
                    }
                }
                // 无论主件附件都是需要加进方案判断的
                plan.addGoods(goods);
                // 看看新生成的计划有没有超过目前的钱
                if (plan.getTotalPrice() <= j * gcd) {
                    // 如果钱够，则比较上个商品使用这么多钱的方案，然后再判断哪个方案的满意度高，择优获取
                    dp[i][j] = ShoppingPlan.max(dp[i - 1][j], plan);
                    continue;
                }
                // 不够钱买新方案的，那就用上个商品在这个钱的方案
                dp[i][j] = dp[i - 1][j];
            }
        }
        // 将最终的方案返回
        return dp[n][m];
    }

    /**
     * 商品
     */
    public static class Goods {
        // 商品编号
        private int id;
        // 商品单价
        private int price;
        // 商品价值（满意度）
        private int value;
        // 商品类型（主件为0，附件大于0）
        private int type;

        public Goods(int id, int price, int value, int type) {
            this.id = id;
            this.price = price;
            this.value = value;
            this.type = type;
        }

        public Goods() {
        }

        public int getId() {
            return this.id;
        }

        public int getPrice() {
            return this.price;
        }

        public int getValue() {
            return this.value;
        }

        public int getType() {
            return this.type;
        }

        /**
         * 商品是否附件
         * @return true/false
         */
        public boolean isAttachment() {
            return this.type > 0;
        }
    }

    /**
     * 购物方案
     */
    public static class ShoppingPlan {
        // 商品列表
        private List<Goods> goodsList;
        // 总金额
        private int totalPrice;
        // 总价值（总满意度）
        private int totalValue;

        /**
         * 构造函数，需要输入方案编号
         */
        public ShoppingPlan() {
            this.goodsList = new ArrayList<Goods>();
            this.totalPrice = 0;
            this.totalValue = 0;
        }

        private ShoppingPlan(List<Goods> goodsList, int totalPrice, int totalValue) {
            this.goodsList = goodsList;
            this.totalPrice = totalPrice;
            this.totalValue = totalValue;
        }

        /**
         * 添加商品，同时会累计总金额和总价值
         * @param goods 商品
         */
        public void addGoods(Goods goods) {
            this.goodsList.add(goods);
            this.totalPrice += goods.getPrice();
            this.totalValue += goods.getValue();
        }

        public int getTotalPrice() {
            return this.totalPrice;
        }

        public int getTotalValue() {
            return this.totalValue;
        }

        /**
         * 判断方案中是否存在当前附件的主件
         * @param attachment 附件商品
         * @return true/false
         */
        public boolean hasMainGoods(Goods attachment) {
            for (Goods mainGoods : this.goodsList) {
                if (mainGoods.getId() == attachment.getType()) {
                    return true;
                }
            }
            return false;
        }

        /**
         * 复制购物方案（不会影响到原购物方案信息）
         * @return 购物方案副本
         */
        public ShoppingPlan createSnapshot() {
            List<Goods> goodsList = new ArrayList<Goods>(this.goodsList.size());
            goodsList.addAll(this.goodsList);
            return new ShoppingPlan(goodsList, this.totalPrice, this.totalValue);
        }

        /**
         * 获取满意度高的方案
         * @param a 购物方案a
         * @param b 购物方案b
         * @return 满意度高的方案
         */
        public static ShoppingPlan max(ShoppingPlan a, ShoppingPlan b) {
            if (a.getTotalValue() >= b.getTotalValue()) {
                return a;
            }
            return b;
        }
    }

    /**
     * 用更相减损法计算公约数
     * @param a 数a
     * @param b 数b
     * @return 最大公约数
     */
    public static int gcd(int a, int b) {
        if (a < b) {
            int tmp = a;
            a = b;
            b = tmp;
        }
        return (a % b == 0) ? b : gcd(a - b, b);
    }

    /**
     * 计算数组里的所有数的最大公约数
     * @param goodsList 源数据数组
     * @return 数组里的所有数的最大公约数
     */
    public static int getArrayGcd(List<Goods> goodsList) {
        int gcd = goodsList.get(0).getPrice();
        for (int i = 1; i < goodsList.size(); i++) {
            gcd = gcd(gcd, goodsList.get(i).getPrice());
        }
        return gcd;
    }
}
